<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Section 5.2.5: Mixed strategies for matrix games</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/cvxbook/Ch05_duality/html/matrix_games.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Section 5.2.5: Mixed strategies for matrix games</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Boyd &amp; Vandenberghe "Convex Optimization"</span>
<span class="comment">% Jo&euml;lle Skaf - 08/24/05</span>
<span class="comment">%</span>
<span class="comment">% Player 1 wishes to choose u to minimize his expected payoff u'Pv, while</span>
<span class="comment">% player 2 wishes to choose v to maximize u'Pv, where P is the payoff</span>
<span class="comment">% matrix, u and v are the probability distributions of the choices of each</span>
<span class="comment">% player (i.e. u&gt;=0, v&gt;=0, sum(u_i)=1, sum(v_i)=1)</span>

<span class="comment">% Input data</span>
randn(<span class="string">'state'</span>,0);
n = 10;
m = 10;
P = randn(n,m);

<span class="comment">% Optimal strategy for Player 1</span>
fprintf(1,<span class="string">'Computing the optimal strategy for player 1 ... '</span>);

cvx_begin
    variable <span class="string">u(n)</span>
    minimize ( max ( P'*u) )
    u &gt;= 0;
    ones(1,n)*u == 1;
cvx_end

fprintf(1,<span class="string">'Done! \n'</span>);
obj1 = cvx_optval;

<span class="comment">% Optimal strategy for Player 2</span>
fprintf(1,<span class="string">'Computing the optimal strategy for player 2 ... '</span>);

cvx_begin
    variable <span class="string">v(m)</span>
    maximize ( min (P*v) )
    v &gt;= 0;
    ones(1,m)*v == 1;
cvx_end

fprintf(1,<span class="string">'Done! \n'</span>);
obj2 = cvx_optval;

<span class="comment">% Displaying results</span>
disp(<span class="string">'------------------------------------------------------------------------'</span>);
disp(<span class="string">'The optimal strategies for players 1 and 2 are respectively: '</span>);
disp([u v]);
disp(<span class="string">'The expected payoffs for player 1 and player 2 respectively are: '</span>);
[obj1 obj2]
disp(<span class="string">'They are equal as expected!'</span>);
</pre>
<a id="output"></a>
<pre class="codeoutput">
Computing the optimal strategy for player 1 ...  
Calling SDPT3: 21 variables, 11 equality constraints
------------------------------------------------------------

 num. of constraints = 11
 dim. of linear var  = 20
 dim. of free   var  =  1 *** convert ublk to lblk
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
    NT      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|6.4e+01|1.9e+01|2.0e+03| 2.875957e-10  0.000000e+00| 0:0:00| chol  1  1 
 1|0.918|0.659|5.2e+00|6.4e+00|5.4e+02| 1.096098e+01 -8.090662e+00| 0:0:00| chol  1  1 
 2|1.000|0.983|2.6e-06|1.2e-01|2.8e+01| 1.127141e+01 -9.363119e+00| 0:0:00| chol  1  1 
 3|1.000|0.795|1.5e-05|2.5e-02|4.7e+00| 2.064202e+00 -2.318812e+00| 0:0:00| chol  1  1 
 4|1.000|0.059|8.2e-07|2.4e-02|3.1e+00| 5.952251e-01 -2.240006e+00| 0:0:00| chol  1  1 
 5|1.000|0.817|1.2e-06|4.4e-03|1.1e+00| 4.136831e-01 -6.778022e-01| 0:0:00| chol  1  1 
 6|0.857|0.466|3.7e-07|2.3e-03|6.1e-01| 2.070733e-01 -3.961679e-01| 0:0:00| chol  1  1 
 7|1.000|0.244|1.7e-07|1.8e-03|4.7e-01| 1.456891e-01 -3.182912e-01| 0:0:00| chol  1  1 
 8|0.877|0.499|9.8e-08|8.8e-04|2.4e-01| 7.303608e-02 -1.654118e-01| 0:0:00| chol  1  1 
 9|1.000|0.298|1.9e-08|6.2e-04|1.7e-01| 5.689301e-02 -1.144651e-01| 0:0:00| chol  1  1 
10|1.000|0.516|8.4e-09|3.0e-04|8.3e-02| 3.785206e-02 -4.426405e-02| 0:0:00| chol  1  1 
11|1.000|0.623|1.8e-09|1.1e-04|3.0e-02| 3.055158e-02  4.199348e-04| 0:0:00| chol  1  1 
12|0.890|0.635|4.3e-10|4.1e-05|1.1e-02| 2.849869e-02  1.779363e-02| 0:0:00| chol  1  1 
13|0.977|0.575|5.8e-11|1.8e-05|4.4e-03| 2.791838e-02  2.355086e-02| 0:0:00| chol  1  1 
14|1.000|0.845|8.6e-12|2.7e-06|6.8e-04| 2.785824e-02  2.718556e-02| 0:0:00| chol  1  1 
15|0.990|0.979|7.8e-13|9.0e-06|1.5e-05| 2.785591e-02  2.784165e-02| 0:0:00| chol  1  1 
16|1.000|0.989|3.9e-15|2.0e-07|3.3e-07| 2.785596e-02  2.785564e-02| 0:0:00| chol  1  1 
17|1.000|0.989|1.4e-15|4.4e-09|6.1e-09| 2.785588e-02  2.785587e-02| 0:0:00|
  stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 17
 primal objective value =  2.78558806e-02
 dual   objective value =  2.78558747e-02
 gap := trace(XZ)       = 6.12e-09
 relative gap           = 5.79e-09
 actual relative gap    = 5.58e-09
 rel. primal infeas     = 1.36e-15
 rel. dual   infeas     = 4.39e-09
 norm(X), norm(y), norm(Z) = 7.8e-01, 5.4e-01, 1.0e+00
 norm(A), norm(b), norm(C) = 1.2e+01, 2.0e+00, 2.4e+00
 Total CPU time (secs)  = 0.18  
 CPU time per iteration = 0.01  
 termination code       =  0
 DIMACS: 1.4e-15  0.0e+00  5.3e-09  0.0e+00  5.6e-09  5.8e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.0278559
 
Done! 
Computing the optimal strategy for player 2 ...  
Calling SDPT3: 21 variables, 11 equality constraints
------------------------------------------------------------

 num. of constraints = 11
 dim. of linear var  = 20
 dim. of free   var  =  1 *** convert ublk to lblk
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
    NT      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|6.8e+01|1.9e+01|2.0e+03|-2.875957e-10  0.000000e+00| 0:0:00| chol  1  1 
 1|0.922|0.672|5.3e+00|6.2e+00|5.3e+02| 1.092866e+01 -8.571052e+00| 0:0:00| chol  1  1 
 2|1.000|0.983|2.0e-06|1.1e-01|2.8e+01| 1.120630e+01 -9.348593e+00| 0:0:00| chol  1  1 
 3|1.000|0.778|1.5e-05|2.6e-02|4.9e+00| 2.004959e+00 -2.556517e+00| 0:0:00| chol  1  1 
 4|1.000|0.059|9.6e-07|2.5e-02|3.4e+00| 6.870092e-01 -2.471033e+00| 0:0:00| chol  1  1 
 5|1.000|0.811|1.4e-06|4.7e-03|1.2e+00| 4.497646e-01 -7.508208e-01| 0:0:00| chol  1  1 
 6|0.788|0.439|4.4e-07|2.7e-03|6.9e-01| 1.587166e-01 -5.229368e-01| 0:0:00| chol  1  1 
 7|1.000|0.243|1.4e-07|2.0e-03|5.4e-01| 9.891092e-02 -4.359698e-01| 0:0:00| chol  1  1 
 8|1.000|0.345|7.1e-08|1.3e-03|4.0e-01| 8.446155e-02 -3.138126e-01| 0:0:00| chol  1  1 
 9|1.000|0.538|2.4e-08|6.1e-04|1.8e-01| 7.060852e-03 -1.681149e-01| 0:0:00| chol  1  1 
10|0.973|0.554|6.6e-09|2.7e-04|7.3e-02|-2.008197e-02 -9.295346e-02| 0:0:00| chol  1  1 
11|1.000|0.259|1.6e-09|2.0e-04|5.5e-02|-2.280391e-02 -7.724443e-02| 0:0:00| chol  1  1 
12|1.000|0.506|9.9e-10|9.9e-05|2.7e-02|-2.599580e-02 -5.299480e-02| 0:0:00| chol  1  1 
13|1.000|0.684|1.2e-10|3.1e-05|8.4e-03|-2.746137e-02 -3.582506e-02| 0:0:00| chol  1  1 
14|1.000|0.570|1.8e-11|1.3e-05|3.5e-03|-2.777472e-02 -3.129383e-02| 0:0:00| chol  1  1 
15|1.000|0.835|5.3e-12|2.2e-06|5.7e-04|-2.785176e-02 -2.842340e-02| 0:0:00| chol  1  1 
16|0.990|0.980|4.2e-13|7.7e-06|1.2e-05|-2.785582e-02 -2.786744e-02| 0:0:00| chol  1  1 
17|1.000|0.989|1.4e-15|1.6e-07|2.7e-07|-2.785581e-02 -2.785607e-02| 0:0:00| chol  1  1 
18|1.000|0.989|7.6e-16|3.6e-09|5.0e-09|-2.785588e-02 -2.785588e-02| 0:0:00|
  stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 18
 primal objective value = -2.78558776e-02
 dual   objective value = -2.78558824e-02
 gap := trace(XZ)       = 4.98e-09
 relative gap           = 4.72e-09
 actual relative gap    = 4.55e-09
 rel. primal infeas     = 7.65e-16
 rel. dual   infeas     = 3.58e-09
 norm(X), norm(y), norm(Z) = 1.0e+00, 4.4e-01, 7.8e-01
 norm(A), norm(b), norm(C) = 1.2e+01, 2.0e+00, 2.4e+00
 Total CPU time (secs)  = 0.19  
 CPU time per iteration = 0.01  
 termination code       =  0
 DIMACS: 7.6e-16  0.0e+00  4.3e-09  0.0e+00  4.5e-09  4.7e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.0278559
 
Done! 
------------------------------------------------------------------------
The optimal strategies for players 1 and 2 are respectively: 
    0.1804    0.0000
    0.0000    0.3254
    0.0000    0.0924
    0.1549    0.0000
    0.1129    0.0000
    0.0000    0.0264
    0.0000    0.4099
    0.1003    0.0509
    0.1474    0.0949
    0.3040    0.0000

The expected payoffs for player 1 and player 2 respectively are: 

ans =

    0.0279    0.0279

They are equal as expected!
</pre>
</div>
</body>
</html>